By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 38, Issue 3, pp. 753-1206

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement

Yaoyun Shi and Yufan Zhu

pp. 753-766

BibTeX  Abstract Full Text:  PDF

I/O-Efficient Planar Separators

Anil Maheshwari and Norbert Zeh

pp. 767-801

BibTeX  Abstract Full Text:  PDF

Approximate Shortest Paths in Anisotropic Regions

Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, and Yajun Wang

pp. 802-824

BibTeX  Abstract Full Text:  PDF

A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover

F. Grandoni, J. Könemann, A. Panconesi, and M. Sozio

pp. 825-840

BibTeX  Abstract Full Text:  PDF

On the Complexity of Verifying Consistency of XML Specifications

Marcelo Arenas, Wenfei Fan, and Leonid Libkin

pp. 841-880

BibTeX  Abstract Full Text:  PDF

Competitive Online Approximation of the Optimal Search Ratio

Rudolf Fleischer, Tom Kamphans, Rolf Klein, Elmar Langetepe, and Gerhard Trippen

pp. 881-898

BibTeX  Abstract Full Text:  PDF

On Approximating the Depth and Related Problems

Boris Aronov and Sariel Har-Peled

pp. 899-921

BibTeX  Abstract Full Text:  PDF

Efficient Algorithms for Description Problems over Finite Totally Ordered Domains

Ángel J. Gil, Miki Hermann, Gernot Salzer, and Bruno Zanuttini

pp. 922-945

BibTeX  Abstract Full Text:  PDF

Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment

C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, and Louxin Zhang

pp. 946-962

BibTeX  Abstract Full Text:  PDF

Simulating Quantum Computation by Contracting Tensor Networks

Igor L. Markov and Yaoyun Shi

pp. 963-981

BibTeX  Abstract Full Text:  PDF

Efficient Colored Orthogonal Range Counting

Haim Kaplan, Natan Rubin, Micha Sharir, and Elad Verbin

pp. 982-1011

BibTeX  Abstract Full Text:  PDF

Finding Branch-Decompositions and Rank-Decompositions

Petr Hliněný and Sang-il Oum

pp. 1012-1032

BibTeX  Abstract Full Text:  PDF

Query-Efficient Algorithms for Polynomial Interpolation over Composites

Parikshit Gopalan

pp. 1033-1057

BibTeX  Abstract Full Text:  PDF

Exact Algorithms for Treewidth and Minimum Fill-In

Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, and Yngve Villanger

pp. 1058-1079

BibTeX  Abstract Full Text:  PDF

Dimensions of Points in Self-Similar Fractals

Jack H. Lutz and Elvira Mayordomo

pp. 1080-1112

BibTeX  Abstract Full Text:  PDF

The Complexity of Monadic Second-Order Unification

Jordi Levy, Manfred Schmidt-Schauß, and Mateu Villaret

pp. 1113-1140

BibTeX  Abstract Full Text:  PDF

The Spectral Method for General Mixture Models

Ravindran Kannan, Hadi Salmasian, and Santosh Vempala

pp. 1141-1156

BibTeX  Abstract Full Text:  PDF

Improved Approximation Algorithms for Broadcast Scheduling

Nikhil Bansal, Don Coppersmith, and Maxim Sviridenko

pp. 1157-1174

BibTeX  Abstract Full Text:  PDF

Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties

Ketan D. Mulmuley and Milind Sohoni

pp. 1175-1206

BibTeX  Abstract Full Text:  PDF